package com.zlk.algorithm.algorithm.dynamicPlan;

// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
public class Code08_DistinctSubsequencesII {


    /**
     * 思路  abaab    去重（重点）
     * 总结计算  纯新  = all-当前字符上次记录
     *               当前字符记录+=纯新
     *               all+=纯新
     *
     *
     *        当前记录就是dp 记录的是加入当前字符 以当前字符结尾的子序列有多少个
     * 从初始位置遍历，定义变量集合 all
     * 假设空集算一个
     * 刚开始就是{ }
     * 从第一个位置开始遍历  原始                         纯新                   当前字符记录           all
     * 遍历1            {}           1                 a   1-0=1              0+1=1             1+1=2
     * 遍历2            {} ,a        2                 b,ab  2-0=2            0+2=2             2+2=4
     * 遍历3            {},a,b,ab    4             a|aa,ba,aba 4-1=3          1+3=4             4+3=7
     * 遍历4    {},a,b,ab,aa,ba,aba  7     a,aa,ba,aba|aaa,baa,abaa  7-4=3
     * @param s
     * @return
     */
    public int distinctSubseqII(String s) {
        int mod = 1000000007;
        char[] str = s.toCharArray();
        int[] cnt = new int[26];
        int all = 1, newAdd;
        for (char x : str) {
            newAdd = (all - cnt[x - 'a'] + mod) % mod;
            cnt[x - 'a'] = (cnt[x - 'a'] + newAdd) % mod;
            all = (all + newAdd) % mod;
        }
        return (all - 1 + mod) % mod;
    }

}
